/**
 * @file bfs.c
 * @brief Breadth-first search for directed graphs, using the
 *	detailed algorithm of Cormen, Leiserson, and Rivest (Introduction to
 *	Algorithms, first edition, p. 532)
 * @author Josh Blomberg @date 2005 
 * <br>$Id: bfs.c 10 2007-06-28 20:08:57Z mfms $
 */

/*
 *  Copyright (C) 2005 Josh Blomberg, Matthias Stallmann
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include <stdio.h>
#include "Gdr.h"

short color[MAX_VERTEX]; /* WHITE if unvisited, GRAY if on stack, BLACK
							       if finished visit */
#define WHITE 0
#define GRAY 1
#define BLACK 2

int dist[MAX_VERTEX];           /* distance from start vertex (mfms) */

 /* declarations and macros for the animation */
#define MSG_SIZE 100 /* maximum length of a message */
char msg[MSG_SIZE];
TWIN pwin; /* window for user prompts */
#define XW 1        /* prompt window coordinates */
#define YW 1
#define init_prompt_window (pwin = create_text_window(XW,YW,""))
#define destroy_prompt_window (kill_window(pwin))
#define wait(msg) (write_text_window(pwin,msg),suspend_animation(),\
				   hide_window(pwin))
#define COUNT 4



// queue entry
typedef struct entry {
	struct entry* pPrev;
    vertex vrtx;
} VERTEX_QUEUE;

VERTEX_QUEUE* g_pQueueHead = NULL;
VERTEX_QUEUE* g_pQueueTail = NULL;

// adds a vertex to the queue head
void ENQUEUE(vertex v)
{
	VERTEX_QUEUE* pNewQueueHead = (VERTEX_QUEUE*)calloc(1, sizeof(VERTEX_QUEUE));
	pNewQueueHead->pPrev = NULL;

	if (g_pQueueHead != NULL)
	{
		g_pQueueHead->pPrev = pNewQueueHead;
	}
	if (g_pQueueTail == NULL)
	{
		g_pQueueTail = pNewQueueHead;
	}
	pNewQueueHead->vrtx = v;
	g_pQueueHead = pNewQueueHead;
}

// removes a vertex from the queue tail
vertex DEQUEUE()
{
	vertex vrtx = g_pQueueTail->vrtx;
	VERTEX_QUEUE *pPrev = g_pQueueTail->pPrev;
	free(g_pQueueTail);
	g_pQueueTail = pPrev;

	if (g_pQueueTail == NULL)    /* added 2005/04/07 (jmblombe)... */
	{
		g_pQueueHead = NULL;
	} /* ...to prevent dangling pointer at head */

	return vrtx;
}
 

// executes a breadth first search starting at vertex u
void BFS(vertex u)
{
  	vertex v; 	/* current other vertex in adjacency list */
  	edge e; 	/* current edge in adjacency list */

  	color[u] = GRAY;
  	expose_vertex_label(u);
   dist[u] = 0;
  	sprintf(msg,"%d",dist[u]);
  	change_vertex_label(u,msg);
  	sprintf(msg,"Start visit, vertex %d\nClick Resume to continue",u);
  	wait(msg);
  	ENQUEUE(u);

  	while (g_pQueueTail != NULL)
  	{
    	u = DEQUEUE();
    	for_adjacent(u,e,v)
		{
	  		blink_edge(e,COUNT);
			if (color[v] == WHITE)
			{
				highlight_edge(e);

				color[v] = GRAY;
            dist[v] = dist[u] + 1;
				expose_vertex_label(v);
  				sprintf(msg,"%d",dist[v]);
  				change_vertex_label(v,msg);
  				sprintf(msg,"Start visit, vertex %d\nClick Resume to continue",v);
  				wait(msg);
				ENQUEUE(v);
			}
		}

		color[u] = BLACK;
		un_highlight_vertex(u);
  		sprintf(msg,"End visit, vertex %d\nClick Resume to continue",u);
  		wait(msg);
    }
}




void animat(void)
{
  	vertex u;
  	edge e;

  	/* initialize the animation */
  	for_all_vertices(u) 
	{
    	highlight_vertex(u);
    	hide_vertex_label(u);
  	}

  	for_all_edges(e) 
	{
    	hide_edge_label(e);
  	}

  	init_prompt_window;

  	for_all_vertices(u) 
	{
    	color[u] = WHITE;
  	}

  	write_text_window(pwin,"Select vertex for starting BFS\ntype `q` to quit");
  	while ((u = select_vertex()) != NULL_VERTEX) 
	{
    	if (color[u] == WHITE) 
		{
      		BFS(u);
      		write_text_window(pwin,"Select another starting vertex\ntype `q` to quit");
    	}
    	else 
		{
      		hide_window(pwin);
      		write_text_window(pwin,"Vertex already visited, try again");
    	}
  	}

  	wait("End of breadth-first search\nClick RESUME to exit animation");

  	for_all_vertices(u) 
	{
    	change_vertex_label(u,"");
    	hide_vertex_label(u);
    	un_highlight_vertex(u);
  	}

  	for_all_edges(e) 
	{
    	change_edge_label(e,"");
    	expose_edge_label(e);
    	un_highlight_edge(e);
  	}

  	destroy_prompt_window;
}



/*  [Last modified: 2007 06 28 at 19:37:48 GMT] */
